package fons.util;

import java.util.Collections;
import java.util.List;

import com.google.common.collect.Lists;

@SuppressWarnings("unused")
public class SuffixTree {
	private Node root = new Node();
	private final String source;

	public SuffixTree (String from) {
		this.source  = from;
		char[] source = (from + "$").toCharArray();

		for (int i = source.length-1; i >= 0; i--) {
			root.addSuffix(source, i, 0);
		}
	}

	public String getSource() {
		return this.source;
	}

	public class Entry {
		private final int start;
		private final int end;
		private final double matching;

		public Entry (int start, int end, double matching) {
			this.start = start;
			this.end = end;
			this.matching = matching;
		}

		public int getPosition() {
			return start;
		}

		public int getEnd() {
			return end;
		}

		public int getLength() {
			return end-start;
		}

		public String getEntry() {
			return source.substring(start, end);
		}
	}

	public List<Integer> getPositionsOf (String s) {
		char[] query = s.toCharArray();
		return root.getPositionsOf(query, 0);
	}

	//Pair<Pair<MatchPercent, Length of string>, List<Positions>>
	public List<Entry> /*Pair<Pair<Double, Integer>, List<Integer>>*/
	findLongestMatchesOf (String s, double percentMatch, int minChars) {
		char[] query = s.toCharArray();
		return root.findLongestMatchesOf (query, 0, percentMatch, minChars);
	}


	public List<Entry> findLongestMatchesOf (String s) {
		return this.findLongestMatchesOf(s, 0.5, 4); 
	}

	public static void main (String[] args) {

		SuffixTree st = new SuffixTree("Wwada");
		String search = "ana";
		List<Entry> matches = st.findLongestMatchesOf(search);
		
	}


	private class Node {
		List<Integer> positions = Lists.newArrayList();
		
		public void addSuffix(char[] source, int position, int step) {
			Edge edge = this.getEdge(source[position+step]);
			this.positions.add(position);

			if (position+step < source.length-1) {
				edge.getChild().addSuffix(source, position, step+1);
			} else {
				leaf = true;
			}
		}
		
		private List<Entry> toEntries (int length, double matchPercent, int minChars) {
			List<Entry> result = Lists.newArrayListWithExpectedSize(positions.size());
			
			if (matchPercent < 1 && length < minChars) {
				return Lists.<Entry>newArrayList();
			}
			
			for (Integer position: positions) {
				result.add(new Entry(position, position + length, matchPercent));
			}
			return result;
		}

		public List<Entry> findLongestMatchesOf(char[] query, int count, double percentMatchRequirement, int minChars) {
			final double matchPercent = count / (double) query.length;
			if (count == query.length) {
				return this.toEntries(count, matchPercent, minChars);
			}				

			for (Edge edge: edges) {
				if (edge.getLabel() == query[count]) {
					return edge.getChild().findLongestMatchesOf(query, count+1, percentMatchRequirement, minChars);
				}
			}

			return matchPercent <= percentMatchRequirement ? 
					Lists.<Entry>newArrayList() : toEntries(count, matchPercent, minChars);
		}

		public List<Integer> getPositionsOf(char[] query, int position) {
			if (position == query.length) return Collections.unmodifiableList(positions);

			for (Edge edge: edges) {
				if (edge.getLabel() == query[position])
					return edge.getChild().getPositionsOf(query, position+1); 
			}

			return Lists.newArrayList();
		}

		public Edge getEdge (char match) {
			for (Edge edge: edges) {
				if (edge.getLabel() == match) {
					return edge;
				}
			}

			Edge newEdge = new Edge(this, match);
			this.edges.add(newEdge);
			return newEdge;
		}

		List<Edge> edges = Lists.newArrayList();

		boolean leaf = false;
		public boolean isLeaf () {
			return leaf;
		}
	}


	private class Edge {
		private Node parent;
		private Node child;
		private char label;

		public Node getParent() {
			return parent;
		}
		public void setParent(Node parent) {
			this.parent = parent;
		}
		public Node getChild() {
			return child;
		}
		public void setChild(Node child) {
			this.child = child;
		}
		public char getLabel() {
			return label;
		}
		public void setLabel(char label) {
			this.label = label;
		}

		public Edge (Node parent, char label) {
			this.parent = parent;
			this.label = label;
			this.child = new Node();
		}
	}
}



